 1.贪心之概述
   
   贪心策略，也被称为贪婪策略。
   什么贪心策略？
   每一步都采取当前状态下最优的选择（局部最优解），从而希望推导出全局最优解
 
 2.案例一
   
   最优装载问题-海盗运货
   海盗们截获了一艘装满各种各样古董的货船,每一件古董都价值连城，
一旦打碎就失去了珍宝的价值 海盗船的载重量为W,每件古董的重量为𝑥i，
海盗们怎么做才能把尽可能多数量的古董装上海盗船？ 
比如 W 为 30，𝑥i 分别为3、5、4、10、7、14、2、11  
   使用贪心策略解决
   选择货物标准：每一次都优先选择重量最小的古董！！ 
   1 、选择重量为 2 的古董，剩重量 28 
   2 、选择重量为 3 的古董，剩重量 25 
   3 、选择重量为 4 的古董，剩重量 21 
   4 、选择重量为 5 的古董，剩重量 16 
   5 、选择重量为 7 的古董，剩重量 9
   结论：按照以上顺序装载货物，并最多装载5件古董！！
   代码实现：
package com.lg.pirate;

import java.util.Arrays;

/**
 * 海盗们截获了一艘装满各种各样古董的货船,每一件古董都价值连城，
 * 一旦打碎就失去了珍宝的价值 海盗船的载重量为W,每件古董的重量为𝑥i，
 * 海盗们怎么做才能把尽可能多数量的古董装上海盗船？
 * 比如 W 为 30，𝑥i 分别为3、5、4、10、7、14、2、11
 */
public class PirateDemo {
    public static void main(String[] args) {
        piratePackage();
    }

    static void piratePackage(){
        //定义载重容量
        int capacity=30;
        //货物
        int[] goods ={3,5,4,10,7,14,2,11};//无序，先进行排序
        Arrays.sort(goods);//升序，由小到大
        //每一次选择当前重量最小的货物装运
//        for (int i = 0; i < goods.length; i++) {
//            System.out.println(goods[i]);
//        }
        // 2,3,4,5,7,10,11,14
        //定义已装载的重量
        int weight=0;
        int numbs=0;
        for (int i = 0; i < goods.length && weight<capacity; i++) {
            int newWeight=weight+goods[i];
            if (newWeight<=30) {
                System.out.println(goods[i]);//打印下当前装载的是哪个货物
                weight=newWeight;
                numbs++; //累计装载的货物数量

            }
        }
        System.out.println("当前装载了" + numbs + "件古董！！！");
    }
}

 3.案例二
   
   零钱兑换
   假设有 25 分、5 分、1 分的硬币，现要找给客户 41 分的零钱，如何办到硬币个数最少？
   贪心策略：
   每一步都优先选择面值最大的硬币
   具体步骤
       选择 25 分的硬币，剩 16 分
       选择 5 分的硬币，剩 11 分
       选择 5 分的硬币，剩 6 分
       选择 5 分的硬币，剩 1 分
       选择 1 分的硬币
   最终的解是 1 枚 25 分、3 枚 5 分、1 枚 1 分的硬币，共 5 枚硬币
   代码实现：
package com.lg.coins;

import java.util.Arrays;

/**
 * 假设有 25 分、5 分、1 分的硬币，现要找给客户 41 分的零钱，如何办到硬币个数最少？
 * -选择 25 分的硬币，剩 16 分
 * -选择 5 分的硬币，剩 11 分
 * -选择 5 分的硬币，剩 6 分
 * -选择 5 分的硬币，剩 1 分
 * -选择 1 分的硬币
 */
public class CoinsDemo {
    //    //定义一个找零钱的方法
//    static void changeCoins(){
//        //准备硬币的面值
//        int[] faces={25,1,5};
//        //总金额
//        int money=41;
//        //记录硬币的个数
//        int coinsNum=0;
//        //每次选择硬币面值最大的
//        Arrays.sort(faces);//默认是升序
//        for (int i = faces.length-1; i >=0; i--) {
//            //判断当前金额与当前面值的关系
//            if (money<faces[i]){
//                continue;
//            }
//            money-=faces[i];//同一个面值可以重复使用
//            coinsNum++;
//            i=faces.length-1;
//        }
//    }
     //定义一个找零钱的方法
    static void changeCoins() {
        //准备硬币的面值
        Integer[] faces = {25, 1, 5};
        //总金额
        int money = 41;
        //记录硬币的个数
        int coinsNum = 0;
        //每次选择硬币面值最大的
        Arrays.sort(faces, (Integer c1, Integer c2) -> {
            return c2-c1;
        });//降序
        //指针
        int i=0;
        while (i<faces.length) {
            //判断当前金额与当前面值的关系
            if (money<faces[i]){
                i++;
                continue;
            }
            money-=faces[i];//同一个面值可以重复使用
            System.out.println(faces[i]);
            coinsNum++;
        }
        System.out.println("一共选择了"+ coinsNum + "个硬币！！");
    }

    public static void main(String[] args) {
        changeCoins();
    }
}
   修改题目
   假设有 25 分、20分， 5 分、1 分的硬币，现要找给客户 41 分的零钱，如何办到硬币个数最少？
   贪心策略：
   每一步都优先选择面值最大的硬币
   具体步骤
       选择 25 分的硬币，剩 16 分
       选择 5 分的硬币，剩 11 分
       选择 5 分的硬币，剩 6 分
       选择 5 分的硬币，剩 1 分
       选择 1 分的硬币
   最终的解是 1 枚 25 分、3 枚 5 分、1 枚 1 分的硬币，共 5 枚硬币
   但是本题的最优解是：2 枚 20 分、1 枚 1 分的硬币，共 3 枚硬币！！！
   贪心策略的优缺点：
       优点
       简单、高效、不需要穷举所有可能，通常作为其他算法的辅助算法来使用
	   缺点
	   目光短浅，不从整体上考虑其他可能，每一步只采取局部最优解，不会对比其他可能性，因此贪心很少情况能
获得最优解。
   使用动态规划算法来解决！！
   